HPAVC/HPAVC CD-ROM.iso/CIS_GAME.ARJ/QMAPS1.THD

Text File | 1993-06-24 | 42KB | 856 lines

______________________ Subj: Globe Surface Modelling ______________________

Fm: Eric J. Floehr 70003,442                   # 186418
To: All                                        Date: 10-Jul-92  14:46:58

Hello,

The discussion about mapping a rectangular surface to a globe representation
on the screen got me thinking that this forum might be a good place to ask a
question I have.  You all seem very knowledgeable and could probably answer
this question!

Basically, I have been working on a plate tectonic model (was inspired by a
program for Xwindows by Dave Allen).  The problem is, that unlike Allen's
model, which uses a rectangular grid, I would like my model to work on a
representation of the surface of a sphere.  This rules out any rectangular
array, because each square would not represent an equal area on the sphere.
And, no "wrapping" rules could be easily constructed.
I know I will need a custom structure, perhaps triangles, with functions to
manipulate a surface or mesh of triangles (ie. each "square" only has 3
shared sides instead of four, which rules out using a standard 2d array).

Anyway, I need to figure out exactly what "mesh" can be used to create an
acurate representation within the computer of the surface of a sphere, with
each "square" of equal area?  Once I have that, I can use the mesh to create
a standard projection to actually present the mesh on the screen.

Any insights, pointers, or references?

Thanks in advance,
Eric
...........................................................................

Fm: Mark Betz/GD SL 76605,2346                 # 187183
To: Eric J. Floehr 70003,442 (X)               Date: 12-Jul-92  20:47:15

Hi, Eric. I'm not the geometry ace around here, but it seems pretty clear
from the outset that you won't be able to use rectangles. Some sort of
triangular structure could be used, as in a geodesic dome. That would
probably be the simplest structure in terms of vertices that need to be
plotted.

I guess we probably need to know more about what you're doing. You said a
"plate tectonics model". I assume you're carving up the surface of the sphere
into plates, and then modeling the forces between them.

                                                        --Mark
...........................................................................

Fm: Eric J. Floehr 70003,442                   # 187382
To: Mark Betz/GD SL 76605,2346 (X)             Date: 13-Jul-92  11:45:17

Mark,

Thanks for the reply!  I hadn't thought about the geodesic dome model, but I
will definately look at how that is constructed to see if it will work as a
structure for it.  You are right, rectangles won't work, but make things a
lot easier! Both in manipulation and display.  I think that is one reason I
am having so much trouble finding any articles or information on using
something other than rectangles!  I've looked for info on how the weather
service, etc. do thier global models, but none of the books went into any
detail.

As for my model, it is going to be a plate tectonic simulator.  It is not
going to be rigorous in that it will use "realistic" modeling: ie. modelling
the convection processes in the mantle, mostly because we know so little
about it.  But it will take into account most of the major known processes
that change the earth: the creation of faults, rift valleys, mountains, etc.
Since no one really knows, say, why a plate splits, etc. that will be fairly
random but modelled in a "realistic" manner.  For example, when a plate
splits, the two plates will always rotate about a point on neither (usually)
plate that can be intersected by the fault line.  This behavior will then
cause other plates to run into each other, or slide past each other.  The
ultimate purpose of this project is not only for obvious educational
purposes, but for those that may wish to "create worlds" with a more
realistic flavor and more "history" than a fractal-based creation.

The next step in the process would be climactic determinations (ie. when,
where, and why an area of land would be a desert, etc.)  But that is a ways
off!

Again, thanks for your help!

-Eric
...........................................................................

Fm: Eric J. Floehr 70003,442                   # 188201
To: Mark Betz/GD SL 76605,2346 (X)             Date: 15-Jul-92  22:35:33

Mark,

I've had a chance to think about the problem of creating a globe structure in
the computer and I've come up with a solution.  I thought about overlaying
triangles and other regular shapes unto a sphere, and thought about the idea
of geodesics.  However, the problem with that is that they aren't squares
(and as you and I know, square representation is much simpler!), and that the
pattern itself would be irregular (ie. you would have to include pointer
information, unlike using a rectangular array where its position determines
its neighbors).  Then of course, one would need an identifier to each
triangle.  Needless to say it wouldn't be an elegant solution.

But while I was thinking about how one would map a point to a particular area
(like a triangle), I thought about how we do it on our globe: latitude and
longitude.  Obviously, the problem with lat and long is that while each lat
division occurs at an equal spacing, the longitudes spread out from the pole
to the equator.

So think of this:  squares can be used to ensircle an area around the
equator, and around the meridian.  If we want to be neat, we could choose the
number of squares such that a square sits over both poles.  Thus, we choose
4, 8, 16, 32, etc. squares to do this.  The squares would not be distorted,
and each square would have an equal area.  Now, the line through the centers
of each square on the equator forms the 0 latitude.  The line through the
first square above the equator on the meridian forms latitude 1, etc.  We
could then string these squares along each latitude, squeezing or streching
each latitude to create an integer number of squares (which would only
incorporate minor and acceptable distortion).

Formally, the number of squares for a given latitude can be found by:

(# squares around eq. & meridian) * cos((360 / # squares) * lat. line)

For example, if we place 16 squares around the meridian and equator:

N. Pole:  1 square
Lat. 3 :  6
Lat. 2 : 11
Lat. 1 : 15
Equator: 16
Lat. -1: 15
Lat. -2: 11
Lat. -3:  6
S. Pole:  1

Then, the only mapping (and it can be a mathmatical rather than physical
mapping) is from one lat. to another.  From long. to long. there is only a
standard array.

Obviously there is some error, since we will end up with "gaps" where
there is a non integer number of squares needed to fill at lat..  These gaps
however, average out.  Look at the chart for the remarkable closeness of fit
of this model:

Circum is the number of squares around the equator and meridian, EF is my
method, and Real is the actual surface area for a sphere of given
circumfrence, and then the error.

Circum:    32  EF:         328  Real:        325.949  Error: 0.6291397%
Circum:    64  EF:        1302  Real:       1303.797  Error: 0.1378507%
Circum:   128  EF:        5218  Real:       5215.189  Error: 0.0538969%
Circum:   256  EF:       20860  Real:      20860.757  Error: 0.0036274%
Circum:   512  EF:       83442  Real:      83443.027  Error: 0.0012305%
Circum:  1024  EF:      333772  Real:     333772.107  Error: 0.0000321%
Circum:  2048  EF:     1335088  Real:    1335088.429  Error: 0.0000321%
Circum:  4096  EF:     5340340  Real:    5340353.715  Error: 0.0002568%
Circum:  8192  EF:    21361402  Real:   21361414.862  Error: 0.0000602%
Circum: 16384  EF:    85445714  Real:   85445659.447  Error: 0.0000638%
Circum: 32768  EF:   341782596  Real:  341782637.787  Error: 0.0000122%
Circum: 65536  EF:  1367130648  Real: 1367130551.148  Error: 0.0000071%

Obviously, a 1024 circumfrence is the last practical one (326K is quite large
for an array!), and the error is 3/100,000 of a percent.

See any flaws?  I haven't but I could be wrong.  Let me know what you think!

Thanks,
-Eric
...........................................................................

Fm: Mark Betz/GD SL 76605,2346                 # 188425
To: Eric J. Floehr 70003,442                   Date: 16-Jul-92  17:26:59

Hi, Eric. I have to be careful here, because I'm more than a bit out of my
league. However, my impression is that you aren't modeling a sphere, but
rather a "wedding cake" arrangement of circular solids. Imagine taking a
cross section of your world bisecting the north and south poles...
                                __
                             __|__|__
                          __|__|__|__|__
                         |__|__|__|__|__|
                            |__|__|__|
                               |__|

As you point out, the result is sort of analogous to aliasing in a digitized
image: you lose some information. How much depends on the size of your
squares. If the resulting resolution is enough for your purposes, then you're
ok.

Another possibility is representing the surface of the globe as a spherical
array of contiguous points in three-space. Given one point, the diameter of
the sphere, and probably some other esoterics of which I'm ignorant, you
could calculate the position of the next point in any direction.

                                                      --Mark
...........................................................................

Fm: Eric J. Floehr 70003,442                   # 188550
To: Mark Betz/GD SL 76605,2346 (X)             Date: 16-Jul-92  23:32:50

Mark,

Whoops!  It seems I didn't really make myself clear, and I appologize.
Actually the idea is not one of cubes, but one of squares.  Remember that I
am trying to model the surface of the sphere, and have no interest in either
its exterior or interior.  Let me explain my model by using a little more
practical example, and hopefully I can articulate this a little better:

Say you have a sphere, that you want to glue squares onto (for whatever
reason) So you cut out squares of the same size, get your glue out, and go to
work.  The easiest and most logical place to start would be the equator.
Lets say we manage it so that it takes exactly 16 squares to go completely
around equator.  There will be some slight overlap since a flat square needs
to fit on a curving surface, but it is minimal and can be ignored.  We do the
same with the meridian, so we have two "equators", one horizontal and one
vertical, intersecting exactly at two places.  Then, since latitude lines
always have equal spacing but longitude lines don't (they are the widest at
the equator and converge to a single point at the poles), we need to start
covering the globe in latitudinal "strips".  So start gluing squares from the
square directly above the equator on the meridian.  As you glue around the
sphere, you will find that after you place your 14th square, there will be
room for about 78% of a 15th square, so you squish the squares so you can fit
15 squares in.  Then, for the square on the meridian above both those lines,
you'll end up with 30% of a square gap after the 11th square, so you'd need
to stretch them a little.  Then, for the next, you'll end up placing 6
squares, with about a 12% of a square gap.  Then you'll have the poles.
Pulling the glued squares from the sphere you'd end up with "strips of
squares" like:
 __
|__|__ __ __ __ __
|__|__|__|__|__|__|__ __ __ __ __
|__|__|__|__|__|__|__|__|__|__|__|__ __ __ __
|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__
|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|
|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|
|__|__|__|__|__|__|__|__|__|__|__|
|__|__|__|__|__|__|
|__|

Obviously, there will be a lot of overlap of the squares on the curves
surface, but this decreases as each square becomes less of a percentage of
the surface area.  Is this clearer?  Let me know if it isn't.

As for projection: a Mercator projection becomes simple:  just take the
graphic above, and stretch each strip horizontally, stretching each square
equally, until they all match up.  Something like:

_______________________________________________
|_______ _______ _______ _______ _______ _______|
|___ ___|____ __|____ __|_ ___ _|_ ____ |__ ____|
|___|___|____|___|___|____|___|___|____|___|____|
|___|__|__|__|__|___|__|__|__|__|___|__|__|__|__|
|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|
|___|__|__|__|__|___|__|__|__|__|___|__|__|__|__|
|___|___|____|___|___|____|___|___|____|___|____|
|_______|_______|_______|_______|_______|_______|
|_______________________________________________|

And, in fact this is how the "mapping" works in going from one latitude to
another: 16 squares at the equator mapped to 15 at latitude 1, 15 mapped to
11, etc.

Then, of course, in the computer each strip is modelled as a 1D array of say
integers, so each square can then contain an altitude, or some other info.

-Eric
...........................................................................

Fm: Mark Betz/GD SL 76605,2346                 # 188579
To: Eric J. Floehr 70003,442 (X)               Date: 17-Jul-92  00:26:54

Hi, Eric. That was a better explanation ( the drawings don't hurt <g> ), but
I think I basically had it the first time. It still looks to me like there's
a problem with the model. Since you've tried to make your concept clearer,
I'll try to do the same for my objection. You've compensated for the varying
diameter of a sphere at different latitudes using varying numbers of squares.
Indeed, you end up with the right value for the circumference of the sphere
at _some_ point along the y-axis of each square. But the problem is that
squares won't map to a sphere. They have to be trapezoids. If you take a set
of your squares as a strip wrapped around the sphere at a given latitude it's
clearer: the circumference of the strip is the same at min and max y, making
it a cylinder, not a section of a sphere. This is what I was trying to
illustrate with the drawing in my reply. To me this seems analogous to the
aliasing that takes place when a smooth curve is rendered into a specific
display resolution. Since you can't represent the smooth, curved surface of a
sphere using squares, what you end up with is a chunky model of a sphere
constructed of cylindrical solids stacked one on top of another. The
resolution of the model will depend on the number and size of the squares.
                                                        --Mark
...........................................................................

Fm: Eric J. Floehr 70003,442                   # 188710
To: Mark Betz/GD SL 76605,2346 (X)             Date: 17-Jul-92  12:44:01

Mark,

Those ASCII drawings sure are tough to make though! <G>  OK, I understand
your point about the overlap, and you are right.  For example, using our 16
square circumfrence model, the circumfrence through the middle of the squares
on the meridian directly above the equator is 14.78 to which we fit 15
squares.  However, the circumfrence at the bottom edge of the squares is
15.69 and at the top it is 13.30 squares.  In other words we would need to
stretch out the bottoms and squish the tops, creating a trapezoidal
structure, rather than a square.  This becomes worse at the pole where the
median is 6.12, but the bottoms are 8.89 and the tops are 3.12 squares.  Do I
understand your argument correctly?  I take your point, and perhaps I was a
little sloppy in my use of geometric figures :)   Saying I use squares and
stretch them and squeeze them to fit is that same as saying I use trapezoids
and stretch and squeeze them a little less.  Physically this matters, but
conceptually it doesn't.  An string of objects around the latitude can be
squares or trapezoids, or better yet a trapezoid that resides in sphere-space
rather than in Euclidean flat-space, the only thing that matters is that the
model must exactly model the sphere when the number of objects goes to
infinity, and that at coarse resolutions, the objects' areas sufficiently
approximate the sphere's surface.  So long as our squares in our model have
an area of 1, it doesn't matter how it gets that area, and you are right in
saying that it would better get that area (and in fact can only get that
area) if the objects are modelled more closely to trapezoids than to squares.

I think we were both dancing around the same point on this issue!

As far as your second issue, I think I understand better what you are getting
at, but I dunno.  But let me make this comment.  We need to make the
distiction between Euclidean flat geometry and sphere (what is the name,
Lympanov?) geometry because they are different and irreconcilable.  That is
why we can never convert exactly between the 2D space of the surface of a
sphere and the 2D space of a flat plane.  My model must reside in
sphere-space, not in flat-space, and therefore the only aliasing done is the
same that is done when converting a space with infinate points into a finite
representation. And you can never ever get around that.

Thanks for your input and suggestions, they have really helped me.  I hope we
can continue this conversation.

-Eric
...........................................................................

Fm: Mark Betz/GD SL 76605,2346                 # 188779
To: Eric J. Floehr 70003,442 (X)               Date: 17-Jul-92  17:40:37

Yep, that's basically what I'm saying. The second "issue" wasn't really an
issue, but rather an attempt at an analogous explanation. If you use squares
to fit the surface of a sphere, you will only be able to approximate the true
shape of it. Similarly a curve cannot be perfectly rendered in pixels. In
this case the pixels are analogous to your squares. The larger the pixels,
the less true the curve; the larger the squares, the less your model will
resemble the true surface of a sphere (which was, after all, Euclid's "most
perfect solid" <g>).

Using trapezoids will yield the same effect, but you will be able to
construct a truer model.

                                                        --Mark
...........................................................................

Fm: Eric J. Floehr 70003,442                   # 188799
To: Mark Betz/GD SL 76605,2346 (X)             Date: 17-Jul-92  18:22:53

Mark,

Its great that we have finally come to terms! <G>  I intend to dabble with
some implementations this weekend and see what I can come up with.  Once I
have the "globe engine", it will be easy to use it for many applications, as
opposed to integrating it with the tectonic simulator, where it can't be used
again.  Of course, then the next part is actually creating the simulation,
which is a different story!  (I wonder how I could relate the tectonic sim to
a game to make it more appropriate for this section?  Escape the Earthquake,
Venture to the Volcano, Find the Fault? :) ).

-Eric
...........................................................................

Fm: Jesse Montrose 76646,3302                  # 188705
To: Eric J. Floehr 70003,442 (X)               Date: 17-Jul-92  12:10:43

Eric,

> We could then string these squares along each latitude, squeezing or
streching each latitude to create an integer number of squares (which would
only incorporate minor and acceptable distortion).

     Don't forget that your "squares" are not at all square once you get off
the equator and meridian.  The closer you get to a pole, the greater the
difference between the bottom & top widths of the shape.  I call it a shape,
because it won't even be a trapezoid, the sides are curved.

        I don't think you should give up on the geodesic model.  You could
still use relatively simple arrays, instead of pointers:

        (just imagine these are real triangles [g])

equator vector:     /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
vector 1      : \/\/\/\/\/\/\/\/\/\/\/\/\/\/     (a little shorter)
vector 2      : /\/\/\/\/\/\/\/\/\/\/\/   (etc..)
        .
        .
        .
pole vector   : \/\/\

For any given triangle, two of it's neighbors will be next to it on the
vector, and the third is just a simple percentage calculation into the
adjacent vector.  If it's too jagged, you can just add  more triangles, until
you can't see the jags anymore... [g]
...........................................................................

Fm: Eric J. Floehr 70003,442                   # 188712
To: Jesse Montrose 76646,3302                  Date: 17-Jul-92  12:52:16

Jesse,

See my latest response to Mark on that.  Basically you are right, but it
doesn't matter what the actual shape is (within reason) so long as its area
in sphere-space is 1.

Thanks for your comments, and I hope to talk with you soon.

-Eric

______________________________ Subj: Hex Maps ______________________________

Fm: William D. Vaughn 74720,1246               # 308941
To: all                                        Date: 05-Mar-93  22:12:41

Can anyone give me some tips on representing (in C or C++) a hex (hexagon)
map sheet?  I would need to determine the range between two hexes and
determine which hexes fall between two hexes (line of sight).

One thing that has occured to me is to just use two-d array:

  hextype map [NROWS][NCOLS];

And then have the routines take into account that every other row is
indented. To see this, imagine a chess board where every other row is
indented half a square.  Each square now touches 6 other squares and you have
something similar to a hex map.  I think I would have serious problems
getting this to work correctly, particularly line of sight.

Another idea: something kind of similar to a linked list:

  struct hextype {
    int terrain, elevation;
    hextype *NW, *NE, *E, *SE, *SW, *W;
  };

This is a little more elegant, but how do you determine range?  If one hex
could tell which of its surrounding hexes is closest to the target, you could
have some sort of recursive function that traces the path between the two,
thus revealing range and line of sight.  But, how do you determine which of
the surrounding hexes is closest to the distant target?  What makes this
method diffcult seems to be that the hexes are so isolated, only having
contact with adjacent hexes.  And, they have no positioning information,
other than relative to the surrounding hexes.

How about something that makes use of the numbers printed on each hex on an
actual map sheet to determine some position information?

If I want to get really abstract, Robert Sedgewick's "Algorithms in C++" has
a section on geometric algorithms, which deal with graphs (sets of vertices)
and determine the shortest route between them, etc.  Even if I could get
something like this to work, seems like it would be overkill for a simple hex
map.

Any suggestions out there?  This is my first post to CIS, so if I've done
something uncool please let me know.

Dominic Vaughn  74720,1246  [e-mail]
...........................................................................

Fm: Bob Provencher/GD SL 71621,2632            # 309235
To: William D. Vaughn 74720,1246 (X)           Date: 06-Mar-93  13:51:52

Hi William, Welcome to GAMERS!  I've thought about this a little bit, and
one idea I've come up with is a 2d array, with a 1/2 square shift on every
other line.  On the even lines, add 1/2 to the array co-ordinate to find the
"real" center of the hex, which can then be used for distance calculations.

I think this will also work for line of sight, if you've got two hexes, then
step through all the hexes in the enclosing rectangle, shifting when
appropriate, and decide how far from the line-of-sight each hex is, by
taking the perpendicular to the line and the hex in question and computing
the distance.  If it's within the .5 "squares" then it's in the line of
sight.

Hope this helps.
Bob
...........................................................................

Fm: William D. Vaughn 74720,1246               # 309447
To: Bob Provencher/GD SL 71621,2632 (X)        Date: 06-Mar-93  20:49:32

Thanks for the advice Bob.  I was leaning towards the 2-d array idea myself,
but it seemed rather difficult because I was thinking of geometric objects
instead of points.  It does seem pretty easy now: each hex's x and y
coordinate are determined by their array index, with every even row adding
0.5 to one of the coordinates.  Range determined by feeding two points into
the distance formula.  And LOS determined by distance between a hex's
coordinates and the line connecting the the other two hexes.

Hopefully it will still seem that simple when I start writing code.  Thanks
again for the help.

Dominic Vaughn
...........................................................................

Fm: yngvi 76703,3046                           # 309244
To: William D. Vaughn 74720,1246 (X)           Date: 06-Mar-93  14:06:06

Your first idea is a good one -- consider the hex map as a brick wall --
alternating rows of overlapped squares or rectangles.  Your graphics can then
display the map as hexagons.

LOS and other direction calculation in hex maps is actually pretty simple if
you use 'slant matrix' calcs.  Unfortunately I dont have the calcs here.
They're pretty basic, but I wouldnt want to guess.  The idea is that you
transform the coordinates in a way that lets you number along diagonals
rather than rows & columns.  once you do that the distance calcs are easier.
LOS is more difficult since you have to check multiple directions, but not
overwhelming.  There were a coupla articles on this in BYTE a long time ago
(early 80's), and I'll try to dig them up.

btw, the LOS calcs in my online sniper game are probably the most complicated
part of the program -- running about 30 pages of code. One big problem is
that calculations are not always reciprocal -- since you're dealing in
discrete units (squares or hexes), diagonal lines are not always duplicated
due to rounding.  So a tree may block when calculated in one direction but
not in the other.  This leads to cases where one player has LOS and the other
doesnt (not appreciated by the second player).  My eventual solution was to
always do both calculations and allow the shot if either player has LOS.
this sometimes leads to odd looking shots, but it makes the game more fair.
...........................................................................

Fm: William D. Vaughn 74720,1246               # 309448
To: yngvi 76703,3046 (X)                       Date: 06-Mar-93  20:49:38

30 pages of LOS code?  Ouch!  I get the feeling mine will be a lot shorter
because my needs are simpler.  For one thing, with the way I have decided to
go (2-d array) it will be very difficult to get LOS to exactly match what I
get with a hex map.  I am trying to write something for BattleTech.  In that
game, if the line connecting the centerpoints of two hexes crosses over even
the tiniest portion of another hex, that hex is in the LOS.

With the method I am going to try (suggested by Bob), a hex is in the LOS if
it's centerpoint is within 0.5 units (half a square) of the line connecting
the other two hexes.  What you end up with is the equivalent of circular
hexes, which is close enough for my needs (I don't need to get the exact same
results as the board game).

Thanks for your advice.  That alternate geometry you mentioned sounded
intertesting.  I guess that would be something oriented towards 60 degree
angles instead of 90 degrees.

Dominic Vaughn
...........................................................................

Fm: yngvi 76703,3046                           # 309772
To: William D. Vaughn 74720,1246               Date: 07-Mar-93  12:56:27

One reason I couldnt use direct lines is speed -- calculating line connecting 2
points requires too much cpu.  So I use a method that's similar to that for
drawing diagonal lines of pixels -- moving one pixel/square at a time, and
incrementing when needed.  That's where the discrepancy comes in -- eg, if
the 2 pts are corners of a 13x3 box, you'd increment every 5:

        Xxxxx........
             xxxxx
                  xxY

  Starting from the other side, you'd see:
        ........xxxxY
           xxxxx
        Xxx..

 So the same squares aren't always checked.  Another problem comes up with
special cases like stone walls:

        ###X###############
            .............Y

Here X is in a window (# = bldg walls).  If you use the normal algorithm for
either of these guys, it would hit a wall at some point and they would be
unable to sight.  So there need to be special routines to handle these sorts
of situations.
...........................................................................

Fm: Dave Menconi 72350,602                     # 310815
To: William D. Vaughn 74720,1246 (X)           Date: 09-Mar-93  01:28:34

My approach to LOS and ranges would be to mimic the calculation you would do
in a board game. I would develop an algorithm that would actual "walk" the
grid from one point to another. For range you count the hexes; for LOS you
look for blocking hexes. For range this would be slower than a mathematical
solution. For LOS I can't see how you can avoid walking the hexes. Since you
have to walk the hexes using a graph would be a pretty good solution (it
seems counter-intuitive -- seems like some kind of array would be better).
You can use a breadth-first search to find the shortest route(s) and then
check to see if any of the hexes are blocked.

Remember that in most games there is some limit to how far you go -- the
weapons have ranges and past those ranges it might as well be infinite. This
means that you can trim the searches. Also, a bredth first search on a 6-way
graph could be pretty costly but you can reduce it if you limit the search to
look only in a particular direction.

Dave
...........................................................................

Fm: William D. Vaughn 74720,1246               # 311370
To: Dave Menconi 72350,602 (X)                 Date: 09-Mar-93  23:53:49

Dave,

I agree with you that having the program walk the hexes is the best way to
determine range and LOS.  I had replied to someone else on this thread that I
was going to try to do everything with simple math: use the distance formula
to calculate range, to determine if a hex blocks LOS calculate it's distance
from line, etc.  Once I started writing the code, I realized that it was just
too unfaithful to the game mechanics of an actual hex map.

In my orignal post I mentioned the possibility of using using graphs and
breadth-first searches.  I am now leaning against this.  For one thing, it
just seems inefficient.  The graph routines are designed for random points
and vertices, and I don't know if there is any way to let them take advantage
of the regularity and structure of a hex map.  The other reason: I've looked
at the code for graphs, and do have a dim understanding of them, but I don't
know if I could write them.

My current plan is to use a 2-d array of hexes.  Each hex would contain,
among other things, an X and Y coordinate.  To walk the map between hexes A
and B, I would:

1. Calculate angle between A and B (using their x and y coordinates)

2. Determine which of the 6 hexes surrounding A is closest to that angle.
   (for example, the angle to the NW hex is 120 degrees, so if the angle
   between A and B is closer to 120 than to 60 or 180, the NW hex would
   be chosen)

3. Call that hex C.  If C=B, we are done.  Otherwise, go to step 1 using
   C and B.

William
...........................................................................

Fm: yngvi 76703,3046                           # 311583
To: William D. Vaughn 74720,1246 (X)           Date: 10-Mar-93  13:43:29

There will still be times when you travers hex edge, rather than move thru
the hex itself. Whenever you traverse a hexside the terrain on both sides is
relevant.  The rules may vary -- it may be that blocking terrain in either
hex will block LOS, or blocking terrain must be in both hexes to block.  So
for every hexside, you will need to start a new thread to follow.

In addition, your calculation of 'best' angle is still going to depend on
which hex you use as your starting point.  Rounding will still be a factor --
eg, the choice of hex used for A to B might not be the same as that for B to
A. This is analogous to drawing a line pixel by pixel.  Since you're mapping
a continuous line to a discrete coordinate system, the result will not be a
smooth line.
...........................................................................

Fm: Dave Menconi 72350,602                     # 310828
To: Bob Provencher/GD SL 71621,2632 (X)        Date: 09-Mar-93  02:36:42

Notwistanding what I said before, I don't think a graph is the way to go. I
reached that conclusion by considering the best way to create a graph. First
you put all the data into an array. Then you make each link a 2 byte index
into the array. That way you save 12 of the 24 bytes. But you might as well
make the array 2 dimentional and make the 2 byte indexes 2 1 byte indexes.
Well, you quickly see that you can calculate the 6 indexes that I was going
to store so you don't need to store them. There you are with your 2
dimentional array...

The way Chris Crawford calculated LOS and range in Tanktics (I didn't write
it but I certainly saw the code) was to calculate a primary and secondary
direction that the target hex has from the starting hex. Then he would look
in each of the two hexes and consider which one had the "best" terrain for
the particular purpose (usually you're trying to figure out more than the
shortest distance -- cover and movement points were also considered). Then he
would step in that direction, find a new primary and secondary hex and do it
again.

If you just want the shortest (in number of hexes) distance you can always
use the "primary" direction and just keep stepping in that direction. You can
get "fewest movement points" using the primary/secondary technique. Note that
a breadth first search will give you a better answer than the primary /
secondary method in some cases but not THAT much better.

I'm sorry but I can't remember what the algorithm for figuring out the
primary and secondary hexes are...
...........................................................................

Fm: Bob Provencher/GD SL 71621,2632            # 311107
To: Dave Menconi 72350,602 (X)                 Date: 09-Mar-93  16:50:43

Hi Dave -

I can't think of any benefits to the graph method.  One idea I had was the
ability to find the shortest non-obstructed path between two hexes, using
matrix representations of each hex, and something called Warshalls
algorithm.  The problem is that the algorithm is O(n^3)!

For line of sight I can't see how the graph would work either.

I guess I need to understand the algorithm your talking about.  It sounds
like it is the same for both the LOS and shortest path calculation, which to
me are very different.

Bob
...........................................................................

Fm: Dave Menconi 72350,602                     # 311399
To: Bob Provencher/GD SL 71621,2632 (X)        Date: 10-Mar-93  01:07:58

Bob,

As I say, it is possible to calculate the range without stepping in each hex;
you can do it mathematically. I don't know the algorithm off hand but I know
that others have found it so it must exist (they think therefor it is? -- no
never mind <G>).

On the other hand, you must step in each hex to get the LOS -- it can't be
done mathematically. So you have to write a "walk the line" routine. Since
you have write one anyway, and since it WILL give you the range (if you write
it so that it will) why not use it to give you the range? It won't be as
efficient but it will be plenty fast enough (it was plenty fast enough on an
Atari 800 and on a Kim -- it will be fast enough on a PC or a Mac!).

The algorithm is so simple it's almost stupid. It's O(n) where n is the
range. The only thing you need (that I don't know how to do) is a routine
that will tell you which of the 6 directions to go in to get from one hex to
another. I think you compare the x and y (actually the delta x and delta y)
but I'm not sure what the exact algorithm is.

Dave
...........................................................................

Fm: yngvi 76703,3046                           # 311584
To: Dave Menconi 72350,602 (X)                 Date: 10-Mar-93  13:43:34

Right, the slant matrix algorithm will give distances by simple addition and
subtraction, so is quite fast.

  Calculating the range is handy to do first, since you can eliminate LOS
calcs for anything out of range.  You can also find the closest (or
strongest, whatever) target in range first, and then do detailed LOS calcs.

 Steve
...........................................................................

Fm: Bob Provencher/GD SL 71621,2632            # 311666
To: Dave Menconi 72350,602 (X)                 Date: 10-Mar-93  17:40:36

Hi Dave -

I'm curious, have you implemented the LOS by walking stepping hexes?  I'd
like to see it because I'm really confused as to how to do it that way.  Or
do you mean you "walk the line" and step through the intersecting hexes?
(That's the way I suggested it be done at the beginning of the thread)

Bob
...........................................................................

Fm: Dave Menconi 72350,602                     # 311974
To: yngvi 76703,3046                           Date: 11-Mar-93  01:10:19

Steve,

It may solve the first problem (hex edge traversal) to have the routine
return 2 hexes -- a primary and a secondary. Perhaps it could also return a
value that indicates how secondary the secondary hex is (i.e. how close to
the hex edge is the line). In cases where the secondary hex is considered
important, one could add a rule that the LOS is blocked only if the primary
and secondary hexes are BOTH blocked.

I would not actually move into the secondary hex and check line of sight
recursively from there because that seems to be a) very expensive in time and
space and b) of marginal value (i.e. only rarely would you get different
results).

Waddaya think? Would this shortcut yield reasonable results?

Now, about your second point (AB isn't the same as BA). Perhaps you could
always draw the line in the same direction. For example, you might always
pick the hex that's farthest up and to the right to start from. That means
that AB still isn't the same as BA but we always calculate AB, never BA so we
always get the same answer. Cheap and dirty but workable, right?

Dave
...........................................................................

Fm: Dave Menconi 72350,602                     # 311973
To: William D. Vaughn 74720,1246 (X)           Date: 11-Mar-93  01:10:11

William,

I'm wondering how you will calculate that angle. Will the standard angle
calculation (arctangent of dy/dx) work in a hex grid!? Also, since you only
need 6 possible angles, it should be possible to simplify the algorithm.

Dave
...........................................................................

Fm: William D. Vaughn 74720,1246               # 312481
To: Dave Menconi 72350,602 (X)                 Date: 12-Mar-93  01:05:32

Dave, yes I used atan (dy/dx), though there were a couple of minor hassles.
For one thing, I had to make adjustments to this if the point did not lie in
quadrant I (eg., for dy and dx both negative I used atan(dy/dx)+PI). Also
dx=0 required special treatment.  I converted the result to degrees.

As for where I got the coordinates: I used the hex's array index.  For
example, the first hex in each row has x=0, the fourth has x=3, etc.  The y
coordinate was a little trickier.  If the distance between hex centers is 1.0
horizontally, it is sqrt(.75) vertically.  I made this a constant (const
double VERTFACT=sqrt(0.75) ) and set each hex's y coordinate to rowNum *
VERTFACT. Also, every odd numbered row is indented by 0.5, or x=x+0.5. Taking
all into account, hex [11][3] has coordinates (11.5, 2.598).

This is about as far as I've gotten.  The next step will be to determine
which of the six directions is closest to the angle between two hexes, which
will simply require rounding the angle to the nearest 60 degrees.  Then it
shouldn't too hard to walk the range! (I hope anyway).

William
...........................................................................

Fm: Dave Menconi 72350,602                     # 311971
To: Bob Provencher/GD SL 71621,2632 (X)        Date: 11-Mar-93  01:10:02

Bob,

I'm talking about "walking the line." I'm sorry, I must have missed your
description.

I think I confused you by talking about the Tanktics movement algorithm. It
would not just travel the straight line between two points but actually try
to find "the best path" according to a set of rules. It was kind of cute
because it would travel through clear terrain at the beginning of the turn
and then "duck into" good cover at the end of the turn so that units were
always in cover when the other player got to shoot. <G>

Dave
...........................................................................

Fm: Bob Provencher/GD SL 71621,2632            # 312225
To: Dave Menconi 72350,602 (X)                 Date: 11-Mar-93  16:47:24

Hi Dave -

Oh ok, I see!  Yeah, ducking into cover is a healthy thing for a unit to do
before the opponents turn <g>.

Bob
...........................................................................